home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Small Eiffel 0.4.8 / lib_std / link2_list.e < prev    next >
Encoding:
Text File  |  1997-04-13  |  3.5 KB  |  174 lines  |  [TEXT/ttxt]
  1. -- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C) 
  2. -- Dominique COLNET and Suzanne COLLIN -- colnet@loria.fr
  3. --
  4. class LINK2_LIST[E]
  5.    -- 
  6.    -- Two way linked list with internal automatic memorization of 
  7.    -- the last access.
  8.    --
  9.  
  10. inherit LINKED_COLLECTION[E] redefine first_link end;
  11.  
  12. creation
  13.    make, from_collection
  14.  
  15. feature {LINKED_COLLECTION}
  16.    
  17.    first_link: LINK2[E];
  18.  
  19. feature -- Creation and Modification :
  20.    
  21.    make is
  22.       -- Make an empty list;
  23.       do
  24.      if first_link /= Void then
  25.         first_link.free;
  26.      end;
  27.      first_link := Void;
  28.      last_link := Void;
  29.      upper := 0;
  30.      mem_idx := 0;
  31.      mem_lnk := Void;
  32.       ensure
  33.      count = 0
  34.       end;
  35.  
  36. feature -- Implementation of deferred :
  37.  
  38.    add_first(element: like item) is
  39.       do
  40.      if first_link = Void then
  41.         !!first_link.make(element,Void,Void);
  42.         last_link := first_link;
  43.         upper := 1;
  44.         mem_idx := 1;
  45.         mem_lnk := first_link;
  46.      else
  47.         !!first_link.make(element,Void,first_link);
  48.         first_link.next.set_previous(first_link);
  49.         upper := upper + 1;
  50.         mem_idx := mem_idx + 1;
  51.      end;
  52.       ensure then
  53.      upper = 1 + old upper 
  54.       end;
  55.  
  56.    add_last(element: like item) is
  57.       do
  58.      if first_link = Void then
  59.         !!first_link.make(element,Void,Void);
  60.         last_link := first_link;
  61.         upper := 1;
  62.         mem_idx := 1;
  63.         mem_lnk := first_link;
  64.      else
  65.         !!last_link.make(element,last_link,Void);
  66.         last_link.previous.set_next(last_link);
  67.         upper := upper + 1;
  68.      end;
  69.       end;
  70.  
  71.    add(element: like item; index: INTEGER) is
  72.       local
  73.      link: like first_link;
  74.       do
  75.      if index = 1 then
  76.         add_first(element);
  77.      elseif index = upper + 1 then
  78.         add_last(element);
  79.      else
  80.         if (index - 1) /= mem_idx then
  81.            go_item(index - 1);
  82.         end;
  83.         !!link.make(element,mem_lnk,mem_lnk.next);
  84.         link.next.set_previous(link);
  85.         mem_lnk.set_next(link);
  86.         upper := upper + 1;
  87.      end;
  88.       end;
  89.  
  90.    remove_first is
  91.       local
  92.      mem: MEMORY;
  93.       do
  94.      if upper = 1 then
  95.         make;
  96.      else
  97.         mem_lnk := first_link;
  98.         first_link := first_link.next;
  99.         first_link.set_previous(Void);
  100.         mem.free(mem_lnk.to_pointer);
  101.         mem_lnk := first_link;
  102.         mem_idx := 1;
  103.         upper := upper - 1;
  104.      end;
  105.       end;
  106.  
  107.    remove(index: INTEGER) is
  108.       local
  109.      mem: MEMORY;
  110.      link: like first_link;
  111.       do
  112.      if index = 1 then
  113.         remove_first;
  114.      elseif index = upper then
  115.         remove_last;
  116.      else
  117.         if (index - 1) /= mem_idx then
  118.            go_item(index - 1);
  119.         end;
  120.         link := mem_lnk.next;
  121.         mem_lnk.set_next(link.next);
  122.         link.next.set_previous(mem_lnk);
  123.         mem.free(link.to_pointer);
  124.         upper := upper - 1;
  125.      end;
  126.       end;
  127.  
  128. feature {NONE}
  129.  
  130.    go_item(index: INTEGER) is
  131.       do
  132.      if index > mem_idx then
  133.         if (upper - index) < (index - mem_idx) then
  134.            from
  135.           mem_idx := upper;
  136.           mem_lnk := last_link;
  137.            until
  138.           index = mem_idx
  139.            loop
  140.           mem_lnk := mem_lnk.previous;
  141.           mem_idx := mem_idx - 1;
  142.            end;
  143.         else
  144.            from
  145.            until
  146.           index = mem_idx
  147.            loop
  148.           mem_lnk := mem_lnk.next;
  149.           mem_idx := mem_idx + 1;
  150.            end;
  151.         end
  152.      elseif (mem_idx - index) < (index - 1) then
  153.         from
  154.         until
  155.            index = mem_idx
  156.         loop
  157.            mem_lnk := mem_lnk.previous;
  158.            mem_idx := mem_idx - 1;
  159.         end;
  160.      else
  161.         from
  162.            mem_idx := 1;
  163.            mem_lnk := first_link;
  164.         until
  165.            index = mem_idx
  166.         loop
  167.            mem_lnk := mem_lnk.next;
  168.            mem_idx := mem_idx + 1;
  169.         end;
  170.      end;
  171.       end;
  172.  
  173. end -- LINK2_LIST[E]
  174.